#include <vector>
using namespace std;
class Solution
{
public:
    int tmp[500010] = {0};
    int mapTmp[500010] = {0};
    // 需要绑定一下该位和排序之后的下标，便于保存最后的结果
    void merge_sort(vector<int> &nums, int left, int right, vector<int> &ans, vector<int> &map)
    {
        if (left >= right)
            return;
        int mid = left + right >> 1;
        merge_sort(nums, left, mid, ans, map);
        merge_sort(nums, mid + 1, right, ans, map);
        int l1 = left, l2 = mid + 1;
        // cout << l1 << ' ' << l2 << endl;
        int k = left;
        // 由于要找右侧小于nums[i]的元素，所以用排降序的方法更加好用
        while (l1 <= mid && l2 <= right)
        {
            // if(l1 == 0 && l2 == 2) cout << nums[l1] << ' ' << nums[l2] << endl;
            // 如果右边比较大，那一定没有逆序对
            if (nums[l2] >= nums[l1])
            {
                // 此时还需要修改一下映射关系，本来在l2位置上的数变到了k上
                mapTmp[k] = map[l2];
                tmp[k++] = nums[l2++];
            }
            else
            {
                // 左边比较大，出现逆序对,跟新保存的逆序对
                mapTmp[k] = map[l1];
                ans[map[l1]] += right - l2 + 1;
                // cout << map[l1] << "---" << right - l2 + 1 << endl;
                tmp[k++] = nums[l1++];
            }
        }
        while (l1 <= mid)
        {
            mapTmp[k] = map[l1];
            tmp[k++] = nums[l1++];
        }
        while (l2 <= right)
        {
            mapTmp[k] = map[l2];
            tmp[k++] = nums[l2++];
        }
        for (int i = left; i <= right; ++i)
        {
            map[i] = mapTmp[i];
            nums[i] = tmp[i];
        }
        // for(auto e: map) cout << e << ' ';
        // cout << endl;
        // for(auto e: nums) cout << e << ' ';
        // cout << endl;
    }
    vector<int> countSmaller(vector<int> &nums)
    {
        int n = nums.size();
        vector<int> ans(n);
        // 保存的是第i位上放的是原数组上的第几个数字
        vector<int> map(n);
        for (int i = 0; i < n; ++i)
            map[i] = i;
        merge_sort(nums, 0, n - 1, ans, map);
        return ans;
    }
};